import random
from functools import cache


def bash_game(n, limit):
    return n % (limit + 1) != 0

def bash_game2(n, limit):
    @cache
    def f(rest):
        if rest == 0: return False
        for pick in range(1, limit+1):
            if not f(rest - pick):
                return True
        return False
    return f(n)

def bash_game3(n, limit):
    sg = [0] * (n+1)
    sg[0] = 0
    for i in range(1, n+1):
        appeared = [False] * (limit+1)
        for j in range(1, limit+1):
            if i - j < 0: break
            appeared[sg[i-j]] = True
        for s in range(limit + 1):
            if not appeared[s]:
                sg[i] = s
                break
    # print(n, limit)
    # print(*[(f'sg({i})', s) for i, s in enumerate(sg)])
    return sg[n] != 0


def test(t):
    for _ in range(t):
        n = random.randint(10, 200)
        limit = random.randint(1, 10)
        r1 = bash_game(n, limit)
        r2 = bash_game2(n, limit)
        r3 = bash_game3(n, limit)
        print(f'{n}个石子，每轮最多拿{limit}个，{"先手" if r1 else "后手"}必胜')
        assert r1 == r2 == r3, f'n: {n},limit: {limit}, r1: {r1}, r2: {r2}, r3: {r3}'


if __name__ == '__main__':
    print(bash_game3(10, 2))
    t = 10000
    test(t)
    print('done')